package dp.LIS;

public class leetcode673最长递增子序列的个数 {
    public int findNumberOfLIS(int[] nums) {
        int length = nums.length;
        // 记录以i结尾的最大长度
        int[] dp = new int[length];
        // 记录最大长度对应序列数量
        int[] counts = new int[length];
        for (int i = 0; i < length; i++) {
            dp[i] = 1;
            counts[i] = 1;
        }
        int max = 1;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        counts[i] = counts[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        counts[i] += counts[j];
                    }
                }
            }
            max = Integer.max(max, dp[i]);
        }
        int res = 0;
        for (int i = 0; i < length; i++) {
            if (dp[i] == max) {
                res += counts[i];
            }
        }
        return res;
    }
}
